/*
 * @lc app=leetcode.cn id=450 lang=golang
 *
 * [450] 删除二叉搜索树中的节点
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
//deleteNode 返回树的根节点
//每一次进行节点连接时，需要生成新的节点，并将原来节点的左右子树指向设置为nil,如果不去除指向，有可能有形成图
func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return root
	}

	if root.Val == key {
		if root.Left == nil && root.Right == nil {
			return nil
		} else if root.Left == nil {
			return root.Right
		} else if root.Right == nil {
			return root.Left
		} else {
			successor := findMinNode(root.Right)
			successor_copy := &TreeNode{Val: successor.Val}
			successor_copy.Left = root.Left
			successor_copy.Right = removeMinNode(root.Right)

			return successor_copy
		}
	} else if key < root.Val {
		root.Left = deleteNode(root.Left, key)
		return root
	} else {
		root.Right = deleteNode(root.Right, key)
		return root
	}
}

func findMinNode(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	for root.Left != nil {
		root = root.Left
	}

	return root
}

//删除最小节点，并返回树新的根节点
func removeMinNode(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	if root.Left == nil {
		return root.Right
	}

	root.Left = removeMinNode(root.Left)
	return root
}

// @lc code=end

